Chapter 10
3D Spherical Geometry Kernel

Table of Contents

10.1   Introduction

The goal of the 3D spherical kernel is to offer to the user a large set of functionalities on spheres, circles and circular arcs in the 3D space. These functionalities require computing on algebraic numbers, which motivates the creation of a new kernel concept extending the CGAL Kernel concept, which is restricted to objects and functionality in a FieldNumberType.

All the choices (interface, robustness, representation, and so on) made here are consistent with the choices made in the CGAL kernel, for which we refer the user to the kernel manual (Chapter 7).

10.2   Spherical Kernel Objects

New main geometric objects are introduced by Spherical_kernel_3: circular arcs ((model of SphericalKernel::CircularArc_3), points of circular arcs (model of SphericalKernel::CircularArcPoint_3), and line segments (model of SphericalKernel::LineArc_3) whose endpoints are points of this new type.

SphericalKernel::CircularArcPoint_3 is used in particular for endpoints of arcs and intersection points between spheres, circles or arcs. The coordinates of these points are algebraic numbers of degree two. Therefore, general predicates offered by the Kernel on Point_3, which have coordinates in a FieldNumberType, would require heavy algebraic computations in algebraic extensions of higher degrees and thus are not provided on them, which explains the need for a new point type.

A consistent set of predicates and constructions is offered on this new type of points. The spherical kernel currently implements a set of fundamental functionalities like intersection, comparisons, inclusion, etc. More might be provided in the future, as long as only algebraic numbers of degree two are used.

10.3   Software Design

The design of Spherical_kernel_3 is similar to the design of Circular_kernel_2 (see Chapter 9). It has two template parameters:

• the first parameter must model the CGAL three dimensional Kernel concept. The spherical kernel derives from it, and it provides all elementary geometric objects like points, lines, spheres, circles and elementary functionality on them.
• the second parameter is the algebraic kernel, which is responsible for computations on polynomials and algebraic numbers. It must model the concept AlgebraicKernelForSpheres. The robustness of the package relies on the fact that the algebraic kernel provides exact computations on algebraic objects.

The 3D spherical kernel uses the extensibility scheme presented in the kernel manual (see Section 7.5). The types of Kernel are inherited by the 3D spherical kernel and some types are taken from the AlgebraicKernelForSpheres parameter. Spherical_kernel_3 introduces new geometric objects as mentioned in Section 10.2.

In fact, the spherical kernel is documented as a concept, SphericalKernel and two models are provided:

• Spherical_kernel_3<Kernel,AlgebraicKernelForSpheres>, the basic kernel,
• and a predefined kernel Exact_spherical_kernel_3.

10.4   Examples

The first example shows how to construct spheres and compute intersections on them using the global function.

File: examples/Circular_kernel_3/intersecting_spheres.cpp

#include <CGAL/Exact_spherical_kernel_3.h>
#include <CGAL/Random.h>

typedef CGAL::Exact_spherical_kernel_3         Spherical_k;

typedef CGAL::Point_3<Spherical_k>             Point_3;
typedef CGAL::Sphere_3<Spherical_k>            Sphere_3;

int main() {

  CGAL::Random generatorOfgenerator;
  int random_seed = generatorOfgenerator.get_int(0, 123456);
  CGAL::Random theRandom(random_seed);
  int count = 0;

  std::cout << "We will compute the approximate probability that 3 spheres wit"
  << "h radius 1 intersect on a 5x5x5 box, it might take some time." << std::endl;

  for(int i=0; i<10000; i++) {

    double x1 = theRandom.get_double(0.0,5.0);
    double y1 = theRandom.get_double(0.0,5.0);
    double z1 = theRandom.get_double(0.0,5.0);
    double r = 1.0;
    double x2 = theRandom.get_double(0.0,5.0);
    double y2 = theRandom.get_double(0.0,5.0);
    double z2 = theRandom.get_double(0.0,5.0);
    double x3 = theRandom.get_double(0.0,5.0);
    double y3 = theRandom.get_double(0.0,5.0);
    double z3 = theRandom.get_double(0.0,5.0);

    Sphere_3 s1 = Sphere_3(Point_3(x1,y1,z1), r);
    Sphere_3 s2 = Sphere_3(Point_3(x2,y2,z2), r);
    Sphere_3 s3 = Sphere_3(Point_3(x3,y3,z3), r);

    std::vector< CGAL::Object > intersecs;
    CGAL::intersection(s1, s2, s3, std::back_inserter(intersecs));
    if(intersecs.size() > 0) count++;
  }

  std::cout << "The approximate probability that 3 spheres with radius 1"
            << std::endl;
  std::cout << "choosen (uniformly) randomly on a 5x5x5 box intersect is: "
            << ((double)count)/((double)(10000)) << std::endl;

  return 0;
}

The second example illustrates the use of a functor.

File: examples/Circular_kernel_3/functor_has_on_3.cpp

#include <CGAL/Exact_spherical_kernel_3.h>
#include <CGAL/Random.h>

typedef CGAL::Exact_spherical_kernel_3         Spherical_k;

typedef CGAL::Point_3<Spherical_k>             Point_3;
typedef CGAL::Circular_arc_3<Spherical_k>      Circular_arc_3;

int main()
{
  int n = 0;
  Circular_arc_3 c = Circular_arc_3(Point_3(10,10,0), Point_3(5,5,5), Point_3(0, 0, 0));
  for(int i = 0; i <= 10; i++) {
    for(int j = 0; j <= 10; j++) {
      for(int k = 0; k <= 10; k++) {
	Point_3 p = Point_3(i, j, k);
	if(Spherical_k().has_on_3_object()(c,p)) {
	  n++;
	  std::cout << "(" << i << "," << j << "," << k << ")" << std::endl;
	}
      }
    }
  }

  std::cout << "There are " << n << " points in the " 
	    << "[0,..,10]x[0,..,10]x[0,...,10] " 
	    << "grid on the circular" << std::endl
	    << " arc defined by the points (10,10,0), (5,5,5), (0,0,0)" 
	    << std::endl << "See the points above." << std::endl;
  return 0;
};

10.5   Design and Implementation History

This package follows the 2D circular kernel package (see Chapter 9), which induced the basic choices of design.

Julien Hazebrouck and Damien Leroy participated in a first prototype. Sylvain Pion is acknowledged for helpful discussions.

This work was partially supported by the IST Programme of the 6th Framework Programme of the EU as a STREP (FET Open Scheme) Project under Contract No IST-006413 (ACS - Algorithms for Complex Shapes).